1. Field of the Invention
This invention relates to a bit plane coding apparatus applied to EBCOT (embedded block coding with optimized truncation), which is one of entropy coding methods.
This application claims priority of Japanese Patent Application No. 2002-092883, filed on Mar. 28, 2002, the entirety of which is incorporated by reference herein.
2. Description of the Related Art
Recently, a static image compression system using discrete wavelet transform called JPEG2000 (ISO/IEC JTC 1/SC 29/WG1) has been proposed.
In JPEG2000, in order to utilize the characteristics of discrete wavelet transform, a coding method called EBCOT (embedded block coding with optimized truncation) is used for entropy coding processing.
EBCOT transforms a multi-valued data sequence to a binary coding sequence by performing two types of processing, that is, bit modeling processing,and arithmetic coding processing. In the case where this EBCOT is applied to a coding algorithm of JPEG2000, processing to generate a binary symbol for arithmetic coding and a context representing its coding system from a multi-valued wavelet coefficient generated by discrete wavelet transform is performed in bit modeling processing, and processing to segment a probability line in accordance with the probability of occurrence of the generated symbol sequence and allocate a binary decimal value indicating a position within a segment to a code corresponding to the code sequence is performed in arithmetic coding processing.
In the coding algorithm of JPEG2000, an area to which wavelet transform has been performed (wavelet transform area) is divided into plural two-dimensional rectangular areas, and EBCOT processing is performed to each of the division units. The rectangular area to which EBCOT has been performed is called code block.
Code Block Division Processing
The code block will now be described.
In JPEG2000, two-dimensional wavelet transform is performed to two-dimensional image data. In two-dimensional wavelet transform, filtering of a wavelet transform region is carried out in the order of the vertical direction and horizontal direction, thus dividing the region into subbands of low-frequency components and high-frequency components. Therefore, the wavelet transform region after wavelet transform is performed has been divided into a subband including a coefficient of a horizontal low-frequency component and a vertical low-frequency component (LL coefficient), a subband including a coefficient of a horizontal high-frequency component and a vertical low-frequency component (HL coefficient), a subband including a coefficient of a horizontal low-frequency component and a vertical high-frequency component (LH coefficient), and a subband including a coefficient of a horizontal high-frequency component and a vertical high-frequency component (HH coefficient). Each subband has resolution that is ½ of that of the wavelet transform region prior to the transform, both vertically and horizontally.
Moreover, in JPEG2000, it is possible to recursively divide the band of two-dimensional data by performing wavelet transform again to the LL coefficient. Therefore, the subband of the LL coefficient is further subdivided into a subband of an LL coefficient, a subband of an HL coefficient, a subband of an LH coefficient and a subband of an HH coefficient. The number of recursive divisions is called resolution level. Resolution level 1 means to perform wavelet transform once to a wavelet transform region. Resolution level 2 means to perform wavelet transform twice to a wavelet transform region.
FIGS. 9 and 10 show the state of a wavelet transform region in the case wavelet transform of resolution level 2 is performed to image data of 4:2:2 format with resolution of 176 horizontal pixels and 144 vertical pixels. FIG. 9 shows a wavelet transform region of a huminance component (Y). FIG. 10 shows a wavelet transform region of color-difference components (Cb, Cr).
As shown in FIGS. 9 and 10, in the wavelet transform region after wavelet transform, a subband of an HL coefficient (1HL), a subband of an LH coefficient (1LH) and a subband of an HH coefficient (1HH) are formed, These subbands are formed by performing the first wavelet transform to the original 4:2:2-format image. Specifically, the resolution of each of the subbands 1HL, 1LH and 1HH is 88 horizontal pixels×vertical 72 pixels for the luminance component and 44 horizontal pixels×36 vertical pixels for the color-difference components.
Moreover, in the wavelet transform region after wavelet transform, a subband of an LL coefficient (2LL), a subband of an HL coefficient (2HL), a subband of an LH coefficient (2LH) and a subband of an HH coefficient (2HH) are formed. These subbands are formed by performing the second wavelet transform to the subband of the LL coefficient (1LL) formed by the first wavelet transform. Each of the subbands 2LL, 2HL, 2LH and 2HH has resolution that is ¼ of that of the original 4:2:2-format image. That is, the resolution of each of the subbands 2LL, 2HL, 2LH and 2HH is 44 horizontal pixels×vertical 36 pixels for the luminance component and 22 horizontal pixels×18 vertical pixels for the color-difference components.
In the case of performing EBCOT in JPEG2000, each of such subbands is further divided into code blocks. The following are division rules for code blocks in JPEG02000.
One code block is necessarily closed within one subband. That is, one code block does not include two or more subbands.
The size of a basic code block is constant irrespective of the size of a subband. The size of a basic code block is, for example, 64×64 pixels.
However, if the size of a basic code block is larger than the size of a subband, the size of the subband itself is the size of the code block. For example, if the size of a subband is smaller than 64×64 pixels, the range of the subband itself becomes a code block.
On the contrary, if the size of a code block is smaller than the size of a subband, plural code blocks are set within one subband. In this case, one or more of the above-described basic code blocks is set within one subband and a code block with a smaller size than that of the basic code block is set in a surplus part. The number of pixels on one side of the code block set in the surplus part is equal to or less than the size of the basic code block (for example, 64×64).
FIGS. 11 and 12 shows specific examples of code blocks set in the wavelet transform region shown in FIGS. 9 and 10.
The subbands 2LL, 2HL, 2LH and 2HH of the luminance component (Y) have a size (43×36) that is smaller than the size of the basic code block (64×64). Therefore, in each of the subbands 2LL, 2HL, 2LH and 2HH of the luminance component (Y), one code block of the same size as each subband is set. That is, the subbands 2LL, 2HL, 2LH and 2HH of the luminance component (Y) are coincident with the code blocks.
The subbands 1HL, 1LH and 1HH of the luminance component (Y) have a size (88×72)that is larger than the size of the basic code block. Therefore, in each of the subbands 1HL, 1LH and 1HH of the luminance component (Y), plural code blocks are set. Specifically, in each of the subbands 1HL, 1LH and 1HH of the luminance component (Y), one code block of 64×64 pixels, one code block of 24×64 pixels, one code block of 64×8 pixels and one code block of 24×8 pixels are set.
All the subbands of the color-difference components (Cr, Cb) have a size that is smaller than the size of the basic code block (64×64). Therefore, in each of the subbands of the color-difference components (Cr, Cb), one code block of the same size as each subband is set.
In this manner, in the wavelet transform region shown in FIGS. 9 and 10, 16 subband are set for the luminance component (Y) and seven subbands are set for each of the two color-difference components (Cr, Cb).
Preprocessing of Bit Modeling
Bit modeling processing in EBCOT will now be described in detail.
The bit modeling processing is the processing to generate a binary symbol for subsequent arithmetic coding and a context representing its coding system from a multi-valued wavelet coefficient, as described above. In other words, the bit modeling processing is the processing to decide a coding system for arithmetic coding.
A coding unit in the bit modeling processing is the above-described code block. Moreover, in the bit modeling processing, coding processing is performed using a unit called bit plane, formed by slicing this code block by bit (by digit).
The multi-valued wavelet coefficient as a coding target of EBCOT is an integer with a positive or negative sing (or an integer expressed in real number). In the bit modeling processing, the multi-valued wavelet coefficient is split into its positive or negative sign and absolute value, which are then coded. For the absolute value part, a bit plane is selected in the order from the upper bit to the lower bit, and each bit is coded while each bit on the bit plane is scanned in a predetermined order.
Each bit within the bit plane as a coding target is coded on the basis of one of the following three types of processing passes:
a significance propagation pass (i.e., a pass for coding an “insignificant” coefficient around which a “significant” coefficient exists);
a magnitude refinement pass (i.e., a pass for coding a “significant” coefficient); and
a cleanup pass (i.e., a pass for coding the remaining coefficient).
There are four types of coding methods carried out in the respective processing passes, that is, zero coding, sign coding, magnitude refinement coding, and run-length coding.
The meaning of a coefficient's being “significant” or “insignificant” is as follows.
Being “significant” is the state where it is found that the value of a target multi-valued wavelet coefficient is not “0” from the result of the coding processing up to this point. In other words, it is the state of the multi-valued wavelet coefficient in which a bit of “1” is found in the procedure of coding while sequentially scanning from the bit plane of the upper bit.
Being “insignificant” is the state where the value of a target multi-valued wavelet coefficient is “0”or can be “0”. In other words, it is the state of the multi-valued wavelet coefficient in which a bit of“1” is not found in the procedure of coding while sequentially scanning from the bit plane of the upper bit.
In the bit modeling processing, initial bit plane search processing is carried out when performing coding in the above-described three processing passes.
The initial bit plane search processing is the processing to detect an “initial bit plane” in each code block. The initial bit plane is the bit plane of the uppermost digit of the bit planes including a bit having a valid value (that is, a bit having a value“1” in the case of positive logic).
The following are the specific processing procedures.
An absolute value component of the wavelet coefficient is extracted and a bit plane is selected for each digit from the uppermost digit (MSB) to the lower digits of the absolute value component. All the bit values within the selected bit planes are searched. In this case, whether or not a “significant” coefficient (a coefficient including a bit that is not “0”) exists in the bit plane is judged. If there is a bit plane in which a “significant” coefficient appears, that is, if a bit plane including a bit having an initial value of “1” is found, this bit plane is used as an initial bit plane.
In the bit modeling processing, coding in the above-described three processing passes is carried out, starting at this initial bit plane. In the bit modeling processing, if bit planes consisting of insignificant bits, that is, bit planes consisting of “0” bits alone continue from MSB, the number of such bit planes is described in a packet header of a coding stream. This value is used in decoding. It is used for forming an all-“0” bit plane and also used for restoring the dynamic range of the multi-valued wavelet coefficient.